dp[0/1][i] :有 i 颗石子 Alice/Bob 为先手,Alice 赢的概率
令 P 为 Alice 拿走石子的概率, Q 为 Bob 拿走石子的概率。
{dp[0][i]=dp[1][i−1]∗P+dp[1][i]∗(1−P)dp[1][i]=dp[0][i−1]∗Q+dp[0][i]∗(1−Q)
尝试化简:
dp[0][i]=dp[1][i−1]∗P+dp[1][i]∗(1−P)
⇒dp[0][i]=dp[1][i−1]∗P+(dp[0][i−1]∗Q+dp[0][i]∗(1−Q))∗(1−P)
⇒dp[0][i]=dp[1][i−1]∗P+dp[0][i−1]∗Q(1−P)+dp[0][i]∗(1−Q)∗(1−P)
⇒dp[0][i](1−(1−P)(1−Q))=dp[1][i−1]∗P+dp[0][i−1]∗Q(1−P)
⇒dp[0][i]=P+Q−PQdp[1][i−1]∗P+dp[0][i−1]∗Q(1−P)
同理可以得到:
dp[1][i]=P+Q−PQdp[0][i−1]∗Q+dp[1][i−1]∗P(1−Q)
边界条件:
dp[0][0]=0,dp[1][0]=1
然后发现可以根据 dp[0/1][i−1] 的大小关系得到 P,Q。
当 dp[0][i−1]>dp[1][i−1],两人都不想拿。
反之两人都想拿。
#include <cstdio>
const int MAXN = 1e5;
int T , n;
double p , q , dp[ 2 ][ MAXN + 5 ];
int main( ) {
scanf("%d",&T);
while( T -- ) {
scanf("%d %lf %lf",&n,&p,&q);
if( n > MAXN ) n = MAXN;
dp[ 0 ][ 0 ] = 0 , dp[ 1 ][ 0 ] = 1;
for( int i = 1 ; i <= n ; i ++ ) {
double P , Q;
if( dp[ 0 ][ i - 1 ] <= dp[ 1 ][ i - 1 ] ) P = p , Q = q;
else P = 1 - p , Q = 1 - q;
dp[ 0 ][ i ] = ( dp[ 1 ][ i - 1 ] * P + dp[ 0 ][ i - 1 ] * Q * ( 1 - P ) ) / ( P + Q - P * Q );
dp[ 1 ][ i ] = ( dp[ 0 ][ i - 1 ] * Q + dp[ 1 ][ i - 1 ] * P * ( 1 - Q ) ) / ( P + Q - P * Q );
}
printf("%.6f\n", dp[ 0 ][ n ] );
}
return 0;
}
/*
1
11115354 0.65433372 0.52248892
0.633701
*/